package study.biggestsequence;

//分治算法，只返回了最大值，没返回区间范围
public class Method3 {

    public static void main(String[] args) {
        double[] array = {1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34.2, 5.4, -7.8,1.1,-4.9};
        System.out.print(maxSubArraySum(array));
    }

    // 分治法求解最大子数组和
    public static double maxSubArraySum(double[] nums) {
        return maxSubArraySumHelper(nums, 0, nums.length - 1);
    }

    // 辅助函数，使用分治法递归求解
    private static double maxSubArraySumHelper(double[] nums, int left, int right) {
        // 基本情况：只有一个元素
        if (left == right) {
            return nums[left];
        }

        // 计算中间点
        int mid = (left + right) / 2;

        // 递归求解左半部分和右半部分的最大子数组和
        double leftMax = maxSubArraySumHelper(nums, left, mid);
        double rightMax = maxSubArraySumHelper(nums, mid + 1, right);

        // 计算跨越中间点的最大子数组和
        double crossMax = maxCrossingSum(nums, left, mid, right);

        // 返回三者中的最大值
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    // 计算跨越中间点的最大子数组和
    private static double maxCrossingSum(double[] nums, int left, int mid, int right) {
        double sum = 0;
        double leftSum = Double.MIN_NORMAL;

        // 从中间向左扫描
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        sum = 0;
        double rightSum = Double.MIN_NORMAL;


        // 从中间向右扫描
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }

        // 返回跨越中间点的最大子数组和
        return leftSum + rightSum;
    }
}
